The present invention relates generally to the electrical, electronic and computer arts, and, more particularly, to geographical information management.
In the era of Big Data and the Internet-of-Things-That-Move, embedded location sensing (e.g., Global Position System or GPS) devices are becoming ubiquitous within smart phones, laptops, smart watches, navigation systems, and even digital cameras. These embedded devices continuously produce time-stamped spatial (i.e. spatiotemporal) data, thus allowing for querying of devices, cars, and/or individuals in motion. Analyzing this data (e.g., extracting patterns) presents significant business opportunities, such as by enabling the resolving of complex problems pertaining to fields including but not limited to crime pattern analysis, epidemic spread characterization, insurance pricing, and traffic congestion prediction.
However, analyzing spatiotemporal data also creates new challenges arising from the overwhelming amounts of such data being produced, as well as the complexity of the queries coupled with processing performance constraints (in many cases real-time). Moreover, the volume of such data is rapidly increasing, especially due to the widespread use of GPS-enabled smart-phones. Thus, new high-performance techniques are needed to attain improved levels of processing performance for spatial (e.g., geographic) queries.
Geohash is a geographic coordinate system which was recently introduced in 2009, and which is widely used for indexing in geographical information systems (GIS). 0/1/2-D geometries can be represented using one or more geohash codes of potentially varying precisions (i.e. code lengths) by encoding a point (0-dimension), line (1-dimension) or 2-D shape as a 2-D shape (collection of boxes) when encoded with geohashes. Geohash codes have many benefits over the conventional longitude latitude system, including integer indexing, arbitrary precision (shortening the code lowers precision), and simple proximity estimation (prefix matching).
However, traditional spatial algorithms operate on data represented using the conventional latitude/longitude geographical coordinate system, and as such spatial predicates on 0/1/2-D geometries are instead evaluated using the Dimensionally Extended Nine-Intersection Model (DE-9IM) matrix, which lacks the aforementioned benefits associated with geohash-coded geometries. Geometries (such as geographical regions) can be represented in several ways, such as by a list of edges (and respective vertices) or by a list of geohash blocks. Spatial predicates are operations applied to determine relations between geometries. Spatial predicates are evaluated using the DE-9IM model for non-geohash-encoded geometries, but there exists no defined mechanism to evaluate spatial predicates on geohash-encoded regions.